#include "avltree.h"

#include <iostream>
#include <cassert>

AvlTree::Node::Node(int itemValue)
: item(itemValue), pLeft(0), pRight(0) {}

AvlTree::AvlTree()
  : m_pRoot(0) 
{}

AvlTree::~AvlTree()
{
  clear();
}


////////////////////////  public accessors  ////////////////////////  
AvlTree::Node* AvlTree::find (int item) const
{
  return 0;
}

void AvlTree::print () const
{
  printTree(m_pRoot);
  std::cout << std::endl;
}

////////////////////////  public modifiers ////////////////////////  
void AvlTree::insert (int item)
{
  insertIntoTree(&m_pRoot, item);  
}

void AvlTree::remove (int item)
{
}

void AvlTree::clear ()
{
  clearTree(&m_pRoot);
}

  ////////////////////////  private accessors //////////////////////// 
void AvlTree::printTree	(Node *pTree) const
{
  if (0 == pTree) return;
  
  std::cout << "(";
  printTree(pTree->pLeft);
  std::cout << ") ";
  
  std::cout<< pTree->item;
  
  std::cout << " (";
  printTree(pTree->pRight);
  std::cout << ")";
}
  
  ////////////////////////  private modifiers ////////////////////////  
void AvlTree::insertIntoTree (Node** ppTree, int item)
{
  assert(ppTree != 0);
  
  if(0 == *ppTree) {
    *ppTree = new Node(item);
  }
  else {
    if(item < (*ppTree)->item) {
      insertIntoTree(&((*ppTree)->pLeft), item);
    }
    else {
      insertIntoTree(&((*ppTree)->pRight), item);
    }
  }
}

void AvlTree::clearTree	(Node** ppTree)
{
  if (0 == *ppTree) return;
  
  clearTree(&((*ppTree)->pLeft));
  clearTree(&((*ppTree)->pRight));
  delete *ppTree;
  *ppTree = 0;
}


////////////////////////////// main ////////////////////////////////  
int main(int argc, char*argv[])
{
  AvlTree tree;	
  tree.insert(1);
  tree.insert(2);
  tree.insert(3);
  tree.insert(4);
  tree.insert(-2);
  tree.insert(-1);
  tree.print();
  tree.clear();
  tree.print();
  
  return 0;
}

